package com.zhanghp.class038;

import java.util.Stack;

/**
 * O(n^2)
 * 用递归函数逆序栈
 *
 * @author zhanghp
 * @since 2024/6/20 15:07
 */
public class Code05_ReverseStackWithRecursive {


    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.add(1);
        stack.add(2);
        stack.add(3);
        stack.add(4);
        reverse(stack);
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
    public static void reverse(Stack<Integer> stack){
        if (stack.isEmpty()) {
            return;
        }else {
            // 获取底部
            int bottom = bottomOut(stack);
            // 将除弹出的底部倒序
            reverse(stack);
            // 添加刚才的弹出的底部
            stack.push(bottom);
        }
    }
    public static int bottomOut(Stack<Integer> stack) {
        Integer pop = stack.pop();
        if (stack.isEmpty()) {
            return pop;
        } else {
            int ans = bottomOut(stack);
            stack.push(pop);
            return ans;
        }
    }
}
